import java.util.Arrays;

public class Test {
    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        return dp(n,memo);
    }

    //定义一个方法dp，表示：有多少种方法爬上n阶阶梯
    public int dp(int n,int[] memo){
        Arrays.fill(memo,-1);
        if(n == 1 || n == 0){
            return 1;
        }
        if(memo[n] != -1){
            return memo[n];
        }
        //写出状态转移方程
        memo[n] = dp(n-1,memo) + dp(n-2,memo);
        return memo[n];
    }
}